import java.util.*;

public class 合并区间 {
    public int[][] merge(int[][] intervals) {
        int n = intervals.length;
        if (n == 1) {
            return intervals;
        }
        // 通过堆来维护
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> {
            return a[0] - b[0];
        });
        List<int[]> ret = new ArrayList<>();
        // 所有元素入堆
        for (int[] arr : intervals) {
            heap.add(arr);
        }
        int[] cur = heap.poll();
        while (!heap.isEmpty()) {
            int[] next = heap.poll();
            if (cur[1] >= next[0]) {
                if (cur[1] < next[1]) {
                    cur[1] = next[1];
                }
            } else {
                ret.add(cur);
                cur = next;
            }
        }
        // 把最后的元素添加进去
        ret.add(cur);
        // 改造成数组
        int[][] ans = new int[ret.size()][2];
        int cnt = 0;
        for (int[] arr : ret) {
            ans[cnt++] = arr;
        }
        return ans;
    }
}
